PRg030 ZS 2017/18 cviceni úterý 9:00

cvičení 3.října

Hledání největšího prvku z N prvků, včetně důkazu, že nejde rychleji
Hledání druhého největšího prvku z 8 prvků
obecně z N prvků - vzoreček
můžete zkusit dokázat, že nejde rychleji (je to těžší)
cesty věží po šachovnici:
cesta je úplná pokud projde každým políčkem právě jednou
cesta je uzavřená pokud je úplná a končí na políčku, které sousedí s tím, kde začíná
pro danou šachovnici můžeme řešit čtyři úlohy:
1. najít nějakou úplnou cestu
2. najít pro zadané políčko úplnou cestu, která na něm začíná
3. najít nějakou uzavřenou cestu
4. najít pro zadané políčko uzavřenou cestu, která na něm začíná
Uvažujme šachovnici 8x8
- na cvičení jsme ukázali, že řešení úlohy 3. řeší i ostatní
- za dcv. řešte tyto čtyři úlohy pro šachovnice:
  - bez levého dolního rohu
  - bez levého dolního rohu a horního pravého rohu
elektrikář
Ve vysokém domě vede ze sklepa na půdu N žilový kabel.
Najděte způsob jakým elektrikář může označit jednotlivé žíly kabelu tak, aby měla každá žíla na půdě stejné označení jako ve sklepě
elektrikář má zdoj a žárovku, aby mohl detekovat zda danou žílou teče proud, může konce žil na půdě a ve sklepě libovolně propojovat.
Snažte se minimalizovat počet cest elektrikáře nahoru/dolů.
Řešte buď pro nějaký konrétní počet žil (např. 19) nebo obecně pro N žilový kabel. Jaká bude závoslost počtu cest na počtu žil?
Vážení koulí
Máme N podezřelých koulí, mezi nimi je nejvýše jedna špatná (tj. lehčí nebo těžší). Pomocí rovnoramenných vah máme na co nejmenší
počet vážení zjistit která ze 2*N+1 možností nastala (buď jsou všechny koule správné nebo je jedna z nich špatná a musíme zjistit nejen,
která to je, ale i zda je lehčí či těžší než správné koule).
Uvažujte dvě varianty zadání: buď máme na počátku kromě podezřelých koulí i nějaké správné nebo nemáme
Pro variantu se správnými koulemi vyjdou hezčí výsledky a výsledky pro variantu bez správným koulí s nich snadno dostaneme.
Na cvičení jsme ukázali, že s jednou správnou koulí umíme úlohu pro jednu podezřelou vyřešit na jedno vážení a pro čtyři podezřelé to umíme na dvě vážení a současně víme, že na dvě vážení to s víc koulemi nejde.
Snažte se najít nějaká zajímavá tvrzení!!!

Za domácí úkol řešte alespoń dva ze tří zadaných problémů, pokyny máte v mailu

cvičení 9.října

podmínky pro udělení zápočtu:
1. aktivní účast na cvičení
2. řešení domácích úkolů a úloh v recodexu
3. zápočtový program
4. test na práci s ukazateli v Pascalu
Registrujte se do systému Recodex!!! Já vás pak zařadím do skupiny patřící k našemu semináři
Čísla v matematice, ve světě a v počítači
- Čísla v počítači zabírají nějaký kus paměti omezené velikosti, nemohou být proto libovolně velká
  při aritmetických operacích může dojít k přetečení => sčítání není asociativní
- hlavní rozdíl mezi
  čísly typu integer - jsou přesná
  čísly typu real - jsou zaokrouhlená ( proto se s nimi jinak zachází např. při I/O operacích
- Při výpočtech s čísly typu real může dojít k zaokrouhlovacím chybám, není proto rozumné testovat výsledky operací na rovnost
- příklady na růst exponenciely
  počet různých vkusů na oblečení ze zadaných N kusů šatstva
Mrkev a petržel
Spočtěte kolika různými způsoby jde osít K záhonů (jsou vedele sebe) mrkvi a petrželí tak, aby nikdy nebyly dva záhony petržel vedle sebe. udělali jsme:
označme
- O(k) počet přípustných osevních plánů k záhonů
- M(k) počet přípustných osevních plánů k záhonů, kde na prvním záhonu je mrkev
- P(k) počet přípustných osevních plánů k záhonů, kde na prvním záhonu je petržel
Pak zřejmě platí: O(k) = M(k)+P(k) , M(1)=P(1)=1 , M(k+1) = O(k) +1 , P(k+1) = M(k)
Velbloud má nosnost 1000 banánů a spotřebu 1 banán na 1 km. Na hromadě je 3000 banánů, najděte způsob, jak do co největší vzdálenosti přepravit 1000 banánů. - vyšešili jsme
Zkuste úlohu řešit obecně
(jak daleko lze donést dané množství banánů a jaké množství banánů jde donést do zadané vzdálenost, oboje pro zadanou nosnost a spotřebu velblouda a velikost hromady na startu)
Dva kameny
Dva hráči hrají následující deskovou hru. Hracím plánem je jedna řada tvořená 1000 políčky, pole jsou očíslována zleva doprava přirozenými čísly od 1 do 1000. Na začátku hry na náhodně zvolených dvou různých polích leží hrací kameny. Výchozí situaci hry lze tedy popsat dvojicí různých celých čísel od 1 do 1000. Oba hráči se ve hře pravidelně střídají. Hráč, který je na tahu, zvolí jeden z kamenů a přemístí ho o libovolný počet polí směrem doleva. Musí přitom kámen posunout alespoň o jedno políčko a zároveň svým tahem nesmí přeskočit jiný hrací kámen ani nesmí umístit přesouvaný kámen na již obsazené políčko. (Tah tedy nelze provést s kamenem stojícím na políčku číslo 1 ani s kamenem stojícím na políčku i, je-li políčko číslo i-1 právě obsazené.) Hra končí ve chvíli, kdy už nelze provést žádný tah, tzn. až se dostanou oba hrací kameny na políčka s čísly 1 a 2. Zvítězil ten z hráčů, který svým tahem dosáhl této koncové situace. Určete, jaké pozice jsou vyhrané a jaké prohrané. Úlohu jsme vyřešili.
Čtyři kameny
Stejná úloha jako byla úloha se dvěmi kameny, ale se čtyřmi hracími kameny. Výchozí situace hry je tedy popsána čtveřicí různých celých čísel od 1 do 1000 (čísla políček, na nichž leží kameny). Hra končí ve chvíli, kdy se hrací kameny dostanou na pole s čísly 1, 2, 3 a 4. Úkolem je opět určit, pro které výchozí situace hry si může zajistit výhru začínající hráč, a nalézt vítěznou strategii hry.
Obdobně tři kameny
Páska
Na políčcích pásky sudé délky jsou napsána nějaká kladná čísla. Dva hráči se střídají ve hře. Hráč na tahu si může vybrat, které z krajních políček pásky si ustřihne. Po skončení hry vyhrál ten z hráčů, kterému se podařilo ustříhat políčka s větším součtem.
Nalezněte jednoduchou!!!! neprohrávající strategii pro hráče, který začíná.
Princezna Mladík se uchází o princeznu. Získá ji, pokud uspěje v následující zkoušce.
Mladíka postaví se zavázanýma očima před otáčecí čtvercový stůl, v jehož rozích stojí 4 sklenice. Každá sklenice může být v jedné ze dvou poloh - dnem vzhůru a dnem dolů. Mladík může v každém kole šáhnout na kterékoli dvě sklenice a podle své vůle případně změnit polohu některých z nich. Účelem je, aby všechny 4 sklenice byly ve stejné poloze. Pokud se to stane - princezna mu to oznámí, on v zkoušce obstál a mohou se chystat zásnuby. Pokud princezna neoznámí úspěch, hra pokračuje dalším kolem. Před tím však sluha stolkem otočí (mladík neví jak).
Poraďte mladíkovi, jak princeznu získat a zjistěte jak dlouho mu to bude trvat.
Domácí úkol - pokyny dostanete v mailu - tvoří:
1. princezna
2. Tři a čtyři kameny
3. Páska
Vězni, žalářníci a lampa - rozmyslet!
Ve vězení je N vězňů odsouzených na doživotí a každý z nich má svou vlastní celu bez oken. Každý den je jeden z vězňů odveden do speciální místnosti, kde je vyslýchán. V této místnosti je na stropě žárovka a na zdi vypínač. Před prvním výslechem je žárovka zhasnutá. Během výslechu může vězeň žárovku pomocí vypínače libovolně rozsvěcet a zhasínat. Když další den přivedou do místnosti dalšího vězně na výslech, tak je žárovka v takovém stavu (rozsvícená nebo zhasnutá), v jakém ji nechal předchozí vězeň. Vězni jsou vyslýcháni v libovolném pořadí a každý z vězňů může být vyslechnut i vícekrát – pokud by výslechy probíhaly po nekonečně mnoho dní, tak by byl každý z vězňů vyslechnut nekonečně krát. Od určitého okamžiku tedy určitě nastane stav, že každý z vězňů byl vyslechnut alespoň jednou. Pokud pak kdykoliv potom kterýkoliv z vězňů během výslechu řekne: „nyní jsme byli všichni vyslechnuti alespoň jednou“, tak budou všichni vězni propuštěni. Pokud někdo tuto větu řekne dříve než je to pravda, tak budou všichni vězni popraveni. Před začátkem výslechů se vězni mohou půl hodiny společně procházet po vězeňském dvoře a domluvit si strategii, jak rozsvěcet a zhasínat žárovku a kdy má někdo pronést propouštěcí formuli. Vaším úkolem je pro vězně tuto strategii vymyslet. K výslechům mohou vězně vodit zcela libovolně, jediným pravidlem, které vyšetřovatelé musí dodržet je, že v libovolném okamžiku musí platit:
" Každý vězeň bude ještě v budoucnu vyslechnut, pokud celý proces neskončí popravou či propuštěním vězňů"
Rozmyslete si i další trvzení o vážení koulí

cvičení 16.října

Zaregistrujte se do recodexu!
pokud vám to nepůjde, vyhledejte pomoc. Pokud by se vám to nepodařilo, napište mi najpozději v sobotu mail a pokud vám to potvrdím, přijďte v pondělí již v 8:30
Pokud jste nestačili poslat minulý úkol, pošlete ho dodatečně
V urně jsou bílé a černé koule. Hráč (do urny nevidí) v každém tahu vybere dvě koule a vrátí jednu podle následujícího předpisu:
B+B vrátí B , B+Č vrátí Č , Č+Č vrátí B (musí mít tedy k dispozici i bílé koule mimo urnu)
zjiste na čem záleží jaká koule zbyde v urně jako poslední.
udělali jsme - invariant "parita počtu černých koulí"
Mince na stole
Hru hrají dva hráči tak, že střídavě pokládají mince na stůl obdélníkového tvaru. všecny mince jsou stejné a nesmí se pokládat na sebe. ten, kdo už nemůže minci na stůl položit prohrál.
Pro koho je hra vyhraná? Udělali jsme - začínající hráč položí minci do středu stolu, tím si díky středové symetrii stlu zajistí, že na každý tah soupeře bude mít odpověď.
Věž z cihel Na okraji stolu stavíme věž z cihel. V každém patře je jedna cihla. Jak daleko od hrany stlo se může věž vzdálit aniž by přepadla?
Pokud zanedbáme kosmologické problémy, pak nekonečně daleko. Zkuste dokázat resp. napsat jednoduchý program, který to ověří.
Efektivní umocńování Kolik je potřeba provést operací násobení pro výpočet N mocniny? Návod byl jak na přednášce, tak na cvičení.
Kulový blesk Jistých N rodin bydlí v bytech, které označíme celými čísly od 1 do N. Rodiny se dohodly provést cyklickou N-směnu bytů (viz též film Kulový blesk). Rodina z bytu číslo 1 chce do bytu číslo 2, rodina z bytu číslo 2 do bytu číslo 3, atd., až rodina z bytu číslo N se bude stěhovat do bytu číslo 1. Výsledné záměny bytů je třeba dosáhnout postupným prováděním dvojsměn. Některé rodiny se tudíž budou během celé akce stěhovat vícekrát. Každá rodina se ale může přestěhovat nejvýše jednou za den. V jednom dni může samozřejmě probíhat souběžně více dvojsměn bytů. Určete, jaký nejmenší počet dní postačí pro dané N k uskutečnění celé zamýšlené akce. Sestavte rozpis, podle něhož je třeba při výměnách bytů postupovat, aby se tohoto minimální počtu dní dosáhlo (tzn. rozpis určující, kdo se který den stěhuje kam).
Synchronizace automatů: Navrhnout konečné automaty G(enerál), Z(adák) a V(oják) tak, aby libolně dlouhá posloupnost vojáků začínající generálem a končící zadákem dokázala vydat salvu za nějakou dobu po generálově rozkazu.
Každý automat může být v jednom z konečné množiny stavů a má v sobě funkci, která na základě jeho vlastního stavu a stavů jeho sousedů určuje nový stav (množna stavů i ona funkce jsou u všech automatů stejné)..
Nejde o přesný popis automatů, ale o myšlenku jejich komunikace
Není to úplně snadné. Kolem roku 1965 uvedl toto cvičení jeden ze zakladatů kybernetiky s tím, že zkušený programátor by to měl vyřešit do 4 hodin. Dnes už je ale základní myšlenka součástí dobrých středoškolských kurzů programování.
Návodná otázka: pokud úloha má řešení, za jak dlouho může k salvě dojít?
Třetí největší číslo z druhého nejdelšího úseku
Na vstupu je poslopnost kladných čísel rozdělení číslem 0 na úseky. kolik potřebujete proměnných ke spočítání daného čísla?
Vstup se může přečíst jen jednou, nepište program, ale napište význam potřebných proměných.
Nejdelší rostoucí vybraná posloupnost
Najděte efektivní algoritmus, který z posloupnsti (uložené v poli) najde nejdelší rostoucí vybraná posloupnost.
Je to známá úloha, nehledejte ji, ale zkuste se zamyslet sami
domácí úkol je:
1. efektivní umocňování
2. Kulový blesk
3. Třetí největší číslo z druhého nejdelšího úseku
Pochopitelně můžete napsat i řešení dalších úloh.
Napíši opět dopis s podrobnostmi.

cvičení 23.října

Rozbor úloh z domácího cvičení:
1. kulový blesk jde za dva dny
2. proměnné pro úlohu s úseky
opětovná formulace úlohy o synchronizaci automatů Argument, že pokud jde automaty zesynchonizovat, nemůže k tomu dojít dřív než za 2*N kroků, kde N je dékla řady
a je jasné, že uotmaty nemohou "spočítat" tuto délku
Ostrý start s recodexem a překladači Pascalu
tři triviální úlohy a jedna středně těžká
Přidám do recodexu ještě jednu "povinnou" úlohu
Zamyslete se nad algoritmickými problémy, které jste neudělali
Vzhledem k tomu, že nám odpadnou dvě cvičení:
1. připravte si otázky k tomu co případně nebude jasné z přednášky
2. Zkuste udělat další "nepovinné" úlohy. Když to nepůjde, nevadí. budeme vědět, co dělá obtíže
3. Pošlu opět mail

PRG030 cvičení 1. ročník informatika - úterý 9:00 SW2

Obsah cvičení